package com.zxy.javaarithmetic.chapter_1_StackQueue;

import java.util.Deque;
import java.util.LinkedList;

/*
 *  @项目名：  study
 *  @包名：    com.zxy.javaarithmetic.chapter_1_StackQueue
 *  @文件名:   P_10_ReduceLessNum
 *  @创建者:   zhangxy
 *  @创建时间:  2018/12/4 15:16
 *  @描述：    TODO
 */
public class P_10_ReduceLessNum {

	public static void main(String[] args) {
		//		int[] arr = new int[100];
		//		for (int i = 0; i < 10; i++) {
		//			arr[i] = (int) (Math.random() * 10 + 1);
		//			System.out.print(arr[i]+" ");
		//		}
		//		System.out.println();
		int[] arr = {8, 3, 5, 3, 2, 8, 8, 2, 4, 3};
		System.out.println("含有满足情况的数组=" + getNum(arr, 5));
	}

	private static int getNum(int[] arr, int num) {
		if (arr == null || arr.length == 0) {
			return 0;
		}
		int lessNum = 0, i = 0, j = 0;
		Deque<Integer> maxQueue = new LinkedList<>();
		Deque<Integer> minQueue = new LinkedList<>();

		while (i < arr.length) {
			while (j< arr.length){
				while (!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[j]) {
					maxQueue.pollLast();
				}
				maxQueue.addLast(j);
				while (!minQueue.isEmpty() && arr[minQueue.peekLast()] >= arr[j]) {
					minQueue.pollLast();
				}
				minQueue.addLast(j);
				if ((arr[maxQueue.peekFirst()] - arr[minQueue.peekFirst()]) > num) {
					break;
				}
				j++;
			}
			lessNum += (j - i);
			if (maxQueue.peekFirst() == i) {
				maxQueue.pollFirst();
			}
			if (minQueue.peekFirst() == i) {
				minQueue.pollFirst();
			}
			i++;
		}

		return lessNum;
//		while (i <= j && j < arr.length) {
//			while (!maxQueue.isEmpty() && arr[maxQueue.peekLast()] <= arr[j]) {
//				maxQueue.pollLast();
//			}
//			maxQueue.addLast(j);
//			while (!minQueue.isEmpty() && arr[minQueue.peekLast()] >= arr[j]) {
//				minQueue.pollLast();
//			}
//			minQueue.addLast(j);
//
//			System.out.println(i + "---" + j + "   " + arr[maxQueue.peekFirst()] + "---" + arr[minQueue
//				.peekFirst()]);
//			if ((arr[maxQueue.peekFirst()] - arr[minQueue.peekFirst()]) > num) {
//				System.out.println(j + "----------" + i);
//				lessNum += (j - i);
//				if (maxQueue.peekFirst() == i) {
//					maxQueue.pollFirst();
//				}
//				if (minQueue.peekFirst() == i) {
//					minQueue.pollFirst();
//				}
//				i++;
//			} else {
//				j++;
//			}
//		}
//
//		while (i < arr.length) {
//			System.out.println(i + "  " + arr[maxQueue.peekFirst()] + "-dadada--" + arr[minQueue.peekFirst()]);
//			if ((arr[maxQueue.peekFirst()] - arr[minQueue.peekFirst()]) <= num) {
//				lessNum += (arr.length - i);
//				if (maxQueue.peekFirst() == i) {
//					maxQueue.pollFirst();
//				}
//				if (minQueue.peekFirst() == i) {
//					minQueue.pollFirst();
//				}
//			}
//			i++;
//		}
//
//		return lessNum;
	}

}
